#include<numeric>
#include<vector>
using namespace std;
class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        vector<int>&v=stones;
        int sum=accumulate(v.begin(),v.end(),0);
        int n=v.size(),m=sum/2;
        vector<vector<bool>>dp(n+1,vector<bool>(m+1));
        dp[0][0]=true;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=m;j++){
                dp[i][j]=dp[i-1][j];
                if(j-v[i-1]>=0)dp[i][j]=(dp[i][j]||dp[i-1][j-v[i-1]]);
            }
        }
        for(int j=m;j>=0;j--){
            if(dp[n][j]){ return sum-2*j;}
        }
        return sum;
    }
};
class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        vector<int>&v=stones;
        int sum=accumulate(v.begin(),v.end(),0);
        int n=v.size(),m=sum/2;
        vector<bool>dp(m+1);
        dp[0]=true;
        for(int i=1;i<=n;i++)
            for(int j=m;j-v[i-1]>=0;j--)
                dp[j]=dp[j]||dp[j-v[i-1]];
        for(int j=m;j>=0;j--)
            if(dp[j]) return sum-2*j;
        return sum;
    }
};